#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ret;
        ret.clear();
        int row = matrix.size();
        if(row == 0) {
            return ret;
        }
        int col = matrix[0].size();
        int ar = 0, ac = 0;
        int br = row-1, bc = col-1;
        while(ar <= br && ac <= bc) {
            //打印左上角:(ar,ac) 右下角:(br,bc) 构成的矩形边框
            getMatrixFrame(matrix, ar, ac, br, bc, ret);
            // cout << endl;
            //向内部移动ar ac br bc
            ar++;
            ac++;
            br--;
            bc--;
        }
        return ret;
    }

    void getMatrixFrame(const vector<vector<int> > &matrix, 
                        int ar, int ac, int br, int bc, vector<int>& ret) {
        if(ar == br) {
            //打印横线
            for(int i = ac; i <= bc; i++) {
                // cout << matrix[ar][i] << " ";
                ret.push_back(matrix[ar][i]);
            }
            return;
        } else if(ac == bc) {
            //打印竖线
            for(int i = ar; i <= br; i++) {
                // cout << matrix[i][ac] << " ";
                ret.push_back(matrix[i][ac]);
            }
            return;
        } else {
            int curR = ar;
            int curC = ac;
            //依次打印四条线
            while (curC <= bc) {
                // cout << matrix[curR][curC] << " ";
                ret.push_back(matrix[curR][curC++]);
            }

            curC--;
            curR++;
            while(curR <= br) {
                // cout << matrix[curR][curC] << " ";
                ret.push_back(matrix[curR++][curC]);
            }

            curR--;
            curC--;
            while(curC >= ac) {
                // cout << matrix[curR][curC] << " ";
                ret.push_back(matrix[curR][curC--]);
            }

            curC++;
            curR--;
            while(curR > ar) {
                // cout << matrix[curR][curC] << " ";
                ret.push_back(matrix[curR--][curC]);
            }            
        }
    }

    void test() {
        vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
        spiralOrder(v);
    }


};

int main() {
    Solution().test();
    return 0;
}